package com.future;

import java.util.HashSet;
import java.util.Set;

/**
 * Description: 576. 出界的路径数
 *
 * @author weiruibai.vendor
 * Date: 2023/2/16 17:07
 */
public class Solution_576 {

    static Solution_576 instance = new Solution_576();

    public static void main(String[] args) {
        int m = 3, n = 4, maxMove = 4, startRow = 0, startColumn = 0;
        //int m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1;
        // int m = 7, n = 6, maxMove = 13, startRow = 0, startColumn = 2;
        System.out.println(instance.findPaths(m, n, maxMove, startRow, startColumn));
        System.out.println(instance.findPaths_dp2(m, n, maxMove, startRow, startColumn));
    }

    public int findPaths_dp2(int m, int n, int maxMove, int startRow, int startColumn) {
        final int MOD = 1000000007;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int outCounts = 0;
        int[][][] dp = new int[maxMove + 1][m][n];
        dp[0][startRow][startColumn] = 1;
        for (int i = 0; i < maxMove; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < n; k++) {
                    int count = dp[i][j][k];
                    if (count > 0) {
                        for (int[] direction : directions) {
                            int j1 = j + direction[0], k1 = k + direction[1];
                            if (j1 >= 0 && j1 < m && k1 >= 0 && k1 < n) {
                                dp[i + 1][j1][k1] = (dp[i + 1][j1][k1] + count) % MOD;
                            } else {
                                outCounts = (outCounts + count) % MOD;
                            }
                        }
                    }
                }
            }
        }
        return outCounts;
    }

    /**
     * 暴力超时
     *
     * @param m
     * @param n
     * @param maxMove
     * @param startRow
     * @param startColumn
     * @return
     */
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        process(m, n, maxMove, startRow, startColumn, "(" + startRow + "," + startColumn + ")");
        return set.size();
    }

    private void process(int m, int n, int maxMove, int curRow, int curCol, String path) {
        boolean isOut = curRow < 0 || curRow >= m || curCol < 0 || curCol >= n;
        if (maxMove <= 0 || isOut) {
            if (isOut) {
                set.add(path + "(" + curRow + "," + curCol + ")");
            }
            return;
        }
        // up
        process(m, n, maxMove - 1, curRow - 1, curCol, path + "(" + (curRow - 1) + "," + curCol + ")");
        // down
        process(m, n, maxMove - 1, curRow + 1, curCol, path + "(" + (curRow + 1) + "," + curCol + ")");
        // left
        process(m, n, maxMove - 1, curRow, curCol - 1, path + "(" + curRow + "," + (curCol - 1) + ")");
        // right
        process(m, n, maxMove - 1, curRow, curCol + 1, path + "(" + curRow + "," + (curCol + 1) + ")");
    }

    public int findPaths_dp(int m, int n, int maxMove, int startRow, int startColumn) {
        process_dp(m, n, maxMove, startRow, startColumn, "(" + startRow + "," + startColumn + ")");
        return set.size();
    }

    private void process_dp(int m, int n, int maxMove, int curRow, int curCol, String path) {
        boolean isOut = curRow < 0 || curRow >= m || curCol < 0 || curCol >= n;
        if (maxMove <= 0 || isOut) {
            if (isOut) {
                set.add(path + "(" + curRow + "," + curCol + ")");
            }
            return;
        }
        // up
        process_dp(m, n, maxMove - 1, curRow - 1, curCol, path + "(" + (curRow - 1) + "," + curCol + ")");
        // down
        process_dp(m, n, maxMove - 1, curRow + 1, curCol, path + "(" + (curRow + 1) + "," + curCol + ")");
        // left
        process_dp(m, n, maxMove - 1, curRow, curCol - 1, path + "(" + curRow + "," + (curCol - 1) + ")");
        // right
        process_dp(m, n, maxMove - 1, curRow, curCol + 1, path + "(" + curRow + "," + (curCol + 1) + ")");
    }

    Set<String> set = new HashSet<>();
}
